/**
 * 129. 求根到叶子节点数字之和
 * https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/
 */
public class Solutions_129 {
    public static void main(String[] args) {
//        String treeStr = "[1 2 3]";  // output: 25  {12 + 13}
//        String treeStr = "[4 9 0 5 1]";  // output: 1026  {495 + 491 + 40}
        String treeStr = "[0 1]";  // output: 1

        TreeNode root = MyTreeNodeUtils.deserialize(treeStr);
        int result = sumNumbers(root);
        System.out.println(result);
    }

    private static int res;
    public static int sumNumbers(TreeNode root) {
        // 类变量还原为 0
        res = 0;
        dfs(root, 0);
        return res;
    }

    static void dfs(TreeNode root, int num) {
        if (root == null) {
            return;
        }
        int cur = num * 10 + root.val;
        if (root.left == null && root.right == null) {
            // 当前递归节点为叶子节点时，将数字
            res += cur;
            return;
        }
        dfs(root.left, cur);
        dfs(root.right, cur);
    }
}
